10996. Проверка авиамаршрутов

Имеются n городов и m авиарейсов. Ваша задача – определить, можно ли, используя доступные рейсы, добраться из любого города в любой другой.

Вход. Первая строка содержит два целых числа n и m – количество городов и рейсов. Города пронумерованы целыми  числами 1, 2, ..., n.

Далее следуют m строк с описанием перелётов. Каждая строка содержит два целых числа a и b, означающих, что существует рейс из города a в город b. Все рейсы являются односторонними.

Выход. Выведите “YES”, если все маршруты возможны, и “NO” в противном случае. В последнем случае также выведите два города a и b, между которыми невозможно совершить путешествие.

Пример входа	Пример выхода
4 5 1 2 2 3 3 1 1 4 3 4	NO 4 2

РЕШЕНИЕ

графы, сильная связность

Анализ алгоритма

В задаче следует вывести “YES”, если граф является сильно связным. Граф называется сильно связным, если для любой его вершины v выполняются следующие условия:

· из вершины v достижимы все остальные вершины графа;

· вершина v достижима из любой другой вершины. Иными словами, из любой вершины существует путь в v, что эквивалентно достижимости по обратным рёбрам.

Зафиксируем вершину v = 1 и проверим выполнение этих условий.

Реализация алгоритма

Входной граф храним в списке смежности g. Обратный граф храним в списке смежности gr.

vector<vector<int> > g, gr;

vector<int> used;

Функция dfs1 выполняет обход графа в глубину.

void dfs1(int v)

{

used[v] = 1;

for (int to : g[v])

if (!used[to]) dfs1(to);

}

Функция dfs2 выполняет обход графа в глубину на обратном графе. 

void dfs2(int v)

{

used[v] = 1;

for (int to : gr[v])

if (!used[to]) dfs2(to);

}

Основная часть программы. Читаем входные данные. Строим обратный граф.

scanf("%d %d", &n, &m);

g.resize(n + 1);

gr.resize(n + 1);

for (i = 0; i < m; i++)

{

scanf("%d %d", &a, &b);

g[a].push_back(b);

gr[b].push_back(a);

}

Запускаем поиск в глубину в исходном графе, начиная с вершины 1.

used.resize(n + 1);

dfs1(1);

for (i = 1; i <= n; i++)

if (used[i] == 0) break;

Если вершина i недостижима (used[i] = 0), то перемещение между городами 1 и i невозможно.

if (i <= n)

{

printf("NO\n%d %d\n", 1, i);

return 0;

}

Запускаем поиск в глубину на обратном графе, начиная с вершины 1.

used.clear();

used.resize(n + 1);

dfs2(1);

for (i = 1; i <= n; i++)

if (used[i] == 0) break;

Если вершина i недостижима из 1 в обратном графе (used[i] = 0), то перемещение между городами i и 1 невозможно.

if (i <= n)

{

printf("NO\n%d %d\n", i, 1);

return 0;

}

Граф является сильно связным. Выводим сообщение “YES”.

printf("YES\n");